package Offer.offer2022;

/**
 * 二叉搜索树的后序遍历序列
 * 后序遍历的特点  根节点在最后
 * 二叉树特点，根节点的左孩子比它小，右孩子比它大
 *
 * @Author: leiwenkang02
 * @Date: 2020/3/27 2:41 下午
 */
public class Test24 {
    public static void main(String[] args) {
        int[] array = {5, 7, 6, 9, 11, 10, 8};
        System.out.println(isBST(array));
    }

    public static boolean isBST(int[] array) {
        if (array == null || array.length == 0) {
            return false;
        }
        return isBST(array, 0, array.length - 1);

    }

    public static boolean isBST(int[] array, int start, int end) {
        if (start == end) {
            return true;
        }
        //最后一个元素为树的根节点
        int rootValue = array[end];
        //比根节点小在其左边
        int i;
        for (i = start; i < end; i++) {
            if (array[i] > rootValue) {
                break;
            }
        }
        //找到分界线后，分界线右边的元素都比其大
        for (int j = i; j < end; j++) {
            if (array[j] <= rootValue) {
                return false;
            }
        }
        //递归判断其左右子树是否都是二叉搜索树
        return isBST(array, start, i - 1) && isBST(array, i, end - 1);
    }
}
